package leetcode.view1715;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	class Node {
		Node[] ccc;

		boolean end;

		public Node() {
			ccc = new Node[26];
			end = false;
		}

		public void add(String word) {
			Node node = this;
			char[] cs = word.toCharArray();
			for (char c : cs) {
				int index = c - 'a';
				if (node.ccc[index] == null) {
					node.ccc[index] = new Node();
				}
				node = node.ccc[index];
			}
			node.end = true;
		}
	}

	public String longestWord(String[] words) {
		Node root = new Node();
		for (String word : words) {
			root.add(word);
		}
		Arrays.sort(words, (a, b) -> a.length() == b.length() ? a.compareTo(b) : b.length() - a.length());
		for (String word : words) {
			char[] cs = word.toCharArray();
			if (this.f(cs, 0, root, 0) > 1) {
				return new String(cs);
			}
		}
		return "";
	}

	private int f(char[] cs, int start, Node root, int size) {
		if (start == cs.length) {
			return size;
		}
		Node node = root;
		for (int i = start; i < cs.length; i++) {
			char c = cs[i];
			int index = c - 'a';
			if (node.ccc[index] == null) {
				return 0;
			}
			node = node.ccc[index];
			if (node.end) {
				int ans = this.f(cs, i + 1, root, size + 1);
				if (ans != 0) {
					return ans;
				}
			}
		}
		return 0;
	}

	@Override
	public void debug1() {
		HelpDebug.compare("dogwalker", this
				.longestWord(HelpDebug.str2array2("[\"cat\",\"banana\",\"dog\",\"nana\",\"walk\",\"walker\",\"dogwalker\"]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
//		char[] cs = "Hello".toCharArray();
//		System.out.println(new String(cs, 1, 0));
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
